An associative memory is a special kind of storage device. Whereas most memories are numerically addressed, associative memories are addressed via their contents. For example, one might ask an associative memory to return all records containing the letters "ZXU" in columns one, two, and three respectively. The address applied to an associative memory is the query. If some record exactly satisfies the query, then the query is said to be exact, otherwise it is said to be inexact. Conventional associative memories provide no information in response to an inexact query. Inexact queries are merely rejected. If a record exists within the associative memory that is only slightly different from the supplied query, then in many cases it would be desirable to know of its existence. Such records are minor corruptions of the query. Alternatively, they are very similar to the query. Some related concepts were discussed in the following articles:
(1) "The application of a pattern matching algorithm to searching medical record text," in the proceedings of the second annual symposium on computer applications in medical care, p. 308-313, IEEE 78CH 1413-3, by the inventor et al, a copy of which is attached hereto and made a part hereof;
(2) The Ramon D. Faulk article in communications of the ACM, Vol. 7/Number II/November 1964, pages 647-653;
(3) The A. J. Szanser article, Mathematical Linguistics Error-Correcting Methods in Natural Language Processing, Information Processing .68-North-Holland Publishing Company-Amsterdam (1969), pages 1412-1416; and
(4) The A. J. Szanser article, The Computer Journal, Vol. 16, Number 2, pages 132-134.
(5) U.S. Pat. Nos. 3,333,243; 3,651,459 and 4,084,260 show the state of the prior art.
(6) "Approximate String Matching", Patrick A. V. Hall and Geoff R. Dowling, ACM Computing Surveys, Vol. 12, No. 4, pp 381-402, December, 1980.
A storage loop is formed when a storage device repeatedly and sequentially transmits its entire contents to external devices over a high speed data bus. An associative memory may be formed by attaching to this bus a device whose function it is to scrutinize in a passive manner the data stream originating from the storage device as it passes by on the bus. This attached device senses data appearing on the bus that is related in some predetermined fashion to a supplied query.
Central to associative memories of this type is some sort of word comparator device. In the prior art, a simple digital comparator distinguishes two cases: equal and unequal. Other devices can detect certain special corruptions such as the transposition of two characters, the deletion of a single character. Still other devices compare two words to arrive at an indication of how similar they are. One such device recodes the words as binary strings and then measures the Hamming distance between them. Devices in the prior art do not, however, seem to compare words in a general way that approaches the sort of similarity recognizing ability found in humans. U.S. Pat. Nos. 3,333,243; 3,651,459; and 4,084,260 show the state of the prior art.
Approximate string matching means which provide a fairly general and sophisticated measure of string similarity exist in prior art. However, in prior art, such systems are relatively slow in completing the matching process. Most of such prior art string matching systems utilize dynamic programming methods as discussed in ACM Computing Surveys in "Approximate String Matching". The computation time for such prior art systems is generally proportional to the square of the average length of the strings.